/**
 * 
 */
package logic;

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

import datamodel.rucksack.Rucksack;
import datamodel.rucksack.RucksackObject;
import datamodel.tree.Tree;
import datamodel.tree.TreeNode;
import datamodel.tree.TreeNodeFactory;
import datamodel.tree.linked.LinkedTree;
import datamodel.tree.sequential.SequentialTree;

/**
 * holds all necessary method to create trees, filter them and find optimal
 * rucksacks
 * 
 * @author Jakob Karolus, Kevin Munk
 * @version 1.0
 * 
 */
public class RucksackTreeBuilder {

	private Tree tree;

	/**
	 * constructor
	 * 
	 * @param flag
	 *            true: uses SequentialTre; false: uses LinkedTree
	 */
	public RucksackTreeBuilder(boolean flag) {
		if (flag) {
			this.tree = new SequentialTree();
		} else {
			this.tree = new LinkedTree();
		}
	}

	/**
	 * creates a tree out of the given RucksackObjects using the following
	 * schematic:<br>
	 * Starting with the first RucksackObject the methods adds it only to the
	 * right node; then processes over the remaining objects
	 * 
	 * @param objects
	 *            the objects to put into the rucksack
	 * @param capacity
	 *            the capacity of the rucksack
	 */
	public void createRucksackTree(Vector<RucksackObject> objects, int capacity) {
		
		Rucksack rucksack = new Rucksack(capacity);
		tree.setCurrentNode(TreeNodeFactory.getNodeForTree(tree, rucksack));
		buildTree(objects, capacity);
	}

	/**
	 * creates a tree out of the given RucksackObjects using the following
	 * schematic:<br>
	 * Starting with the first RucksackObject the methods adds it only to the
	 * right node; then processes over the remaining objects.<br>
	 * The method findOptimalRucksack() on this tree always delivers a rucksack with the given
	 * neededObjects
	 * 
	 * @param objects
	 *            the objects to put into the rucksack
	 * @param neededObjects
	 *            the objects that MUST be in the rucksack at all costs
	 * @param capacity
	 *            the capacity of the rucksack
	 * @throws IllegalArgumentException
	 *             if the neededObjects don't fit into the rucksack
	 */
	public void createRucksackTree(Vector<RucksackObject> objects,
			Vector<RucksackObject> neededObjects, int capacity) {
		
		Rucksack rucksack = new Rucksack(capacity);
		int neededObjectsWeight = 0;
		for(RucksackObject e: neededObjects) {
			neededObjectsWeight += e.getWeight(); 
			rucksack.insert(e);
			// Vorausgesetzt die Objekte befinden sich in beiden Vektoren
			objects.remove(e);
		}
		
		if(neededObjectsWeight > capacity)
			throw new IllegalArgumentException("needed Objects don't fit!");
		
		tree.setCurrentNode(TreeNodeFactory.getNodeForTree(tree, rucksack));
		buildTree(objects, capacity);

	}

	/**
	 * goes recursively over all nodes of the tree and finds the best rucksack
	 * in the leafs.
	 * 
	 * @return the rucksack with the best value. The method returns null, if no
	 *         root exists
	 */
	public Rucksack findOptimalRucksack() {
		boolean compare = true;
		List<TreeNode> visited = new ArrayList<TreeNode>();
		Rucksack rucksack = new Rucksack(0);
		
		while(compare) {
			
			TreeNode leftNode = makeLeftChild();
			TreeNode rightNode = makeRightChild();
			
			if(!tree.hasLeftNode() && !tree.hasRightNode()) {
				if(tree.getCurrentNode().getRucksack().getValue() > rucksack.getValue()) {
					rucksack = tree.getCurrentNode().getRucksack();
				}
				visited.add(tree.getCurrentNode());
				tree.moveToParentNode();
			}
			else if(!visited.contains(leftNode) && tree.moveToLeftNode());
			else if(!visited.contains(rightNode)&& tree.moveToRightNode());
			else if(visited.contains(leftNode) && visited.contains(rightNode) && tree.hasParentNode()) {
				visited.add(tree.getCurrentNode());
				tree.moveToParentNode();
			}
			else if(!tree.moveToParentNode())
				compare = false;
		}
		return rucksack;
	}

	/**
	 * filters the given tree<br>
	 * each rucksack which doesn't fullfill the constraints not part of the list<br>
	 * 
	 * @param constraints
	 *            the constraints to use, if null the constraints are
	 *            irrelevant.
	 * @return a list containing the filtered rucksacks
	 */
	public Vector<Rucksack> filter(Constraints constraints) {
		int maxO = constraints.getMaxObjects();
		int minO = constraints.getMinObjects();
		int maxV = constraints.getMaxValue();
		int minV = constraints.getMinValue();
		
		boolean compare = true;
		List<TreeNode> visited = new ArrayList<TreeNode>();
		Vector<Rucksack> filtersnake = new Vector<Rucksack>();
	
		try {
			if (tree.getCurrentNode() == null);
		} catch (Exception e) {
			return filtersnake;
		}
		while(compare) {

			TreeNode leftNode = makeLeftChild();
			TreeNode rightNode = makeRightChild();
			
			if(!tree.hasLeftNode() && !tree.hasRightNode()) {
				Rucksack rucksack = tree.getCurrentNode().getRucksack();
				if(rucksack.getValue() <= maxV && rucksack.getValue() >= minV 
						&& rucksack.getSize()>= minO && rucksack.getSize()<= maxO) {
					if(!filtersnake.contains(rucksack))
						filtersnake.add(rucksack);
				}
				visited.add(tree.getCurrentNode());
				tree.moveToParentNode();
			}
			else if(!visited.contains(leftNode) && tree.moveToLeftNode());
			else if(!visited.contains(rightNode)&& tree.moveToRightNode());
			else if(visited.contains(leftNode) && visited.contains(rightNode) && tree.hasParentNode()) {
				visited.add(tree.getCurrentNode());
				tree.moveToParentNode();
			}
			else if(!tree.moveToParentNode())
				compare = false;
		}
		return filtersnake;
	}

	/**
	 * @return the current tree of this builder
	 */
	public Tree getTree() {
		return tree;
	}
	
	
	/**
	 * Erstellt von der Wurzel aus den restlichen Baum
	 * @param objects die Objekte die in den Rucksack sollen
	 * @param capacity die Kapazität des Rucksacks
	 */
	private void buildTree(Vector<RucksackObject> objects, int capacity) {
		for(RucksackObject object: objects) {

			Rucksack rucksack = new Rucksack(capacity);
			boolean build = true;
			List<TreeNode> visited = new ArrayList<TreeNode>();

			while(build) {
				
				TreeNode leftNode = makeLeftChild();
				TreeNode rightNode = makeRightChild();
				
				if(!tree.hasLeftNode() && !tree.hasRightNode()) {
					rucksack = new Rucksack(tree.getCurrentNode().getRucksack());
					tree.setLeftNode(TreeNodeFactory.getNodeForTree(tree, rucksack));
					
					rucksack = new Rucksack(rucksack);
					if(rucksack.insert(object)) {
						tree.setRightNode(TreeNodeFactory.getNodeForTree(tree, rucksack));
						tree.moveToRightNode();
						visited.add(tree.getCurrentNode());
						tree.moveToParentNode();
					}
					visited.add(tree.getCurrentNode());
					
					tree.moveToLeftNode();
					visited.add(tree.getCurrentNode());
					tree.moveToParentNode();
				}
				else if(!visited.contains(leftNode) && tree.moveToLeftNode());
				else if(!visited.contains(rightNode)&& tree.moveToRightNode());
				else if(visited.contains(leftNode) && visited.contains(rightNode) && tree.hasParentNode()) {
					visited.add(tree.getCurrentNode());
					tree.moveToParentNode();
				}
				else if(!tree.moveToParentNode())
					build = false;
			}
		}
	}
	
	
	public TreeNode makeLeftChild(){		
		TreeNode leftNode = null;
		if(tree.hasLeftNode()) {
			tree.moveToLeftNode();
			leftNode = tree.getCurrentNode();
			tree.moveToParentNode();
		}
		return leftNode;
	}
	
	
	public TreeNode makeRightChild(){
		TreeNode rightNode = null;
		if(tree.hasRightNode()) {
			tree.moveToRightNode();
			rightNode = tree.getCurrentNode();
			tree.moveToParentNode();
		}
		return rightNode;
	}
}
